/*
 * @Author: szx
 * @Date: 2021-10-30 13:09:15
 * @LastEditTime: 2021-10-30 13:35:15
 * @Description:
 * @FilePath: \leetcode\1-99\19\19.cpp
 */
#include <iostream>
using namespace std;
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};
// class Solution {
//    public:
//     ListNode* removeNthFromEnd(ListNode* head, int n) {
//         ListNode* ptr = head;
//         int cnt = 0;
//         while (ptr != nullptr) {
//             cnt++;
//             ptr = ptr->next;
//         }
//         ListNode* bh = new ListNode(0, head);
//         ListNode* cur = bh;
//         for (int i = cnt; i > 0; i--) {
//             if (n == i) {
//                 cur->next = cur->next->next;
//                 return bh->next;
//             }
//             cur = cur->next;
//         }
//         return bh->next;
//     }
// };
// class Solution {
//    public:
//     ListNode* removeNthFromEnd(ListNode* head, int n) {
//         ListNode* slow = head;
//         ListNode* fast = head;
//         int cnt = 0;
//         while (fast != NULL && fast->next != NULL) {
//             cnt++;
//             slow = slow->next;
//             fast = fast->next->next;
//         }
//         cnt *= 2;
//         if (fast != nullptr) {
//             cnt += 1;
//         }
//         cout << cnt << endl;
//         ListNode* bh = new ListNode(0, head);
//         ListNode* cur = bh;
//         for (int i = cnt; i > 0; i--) {
//             if (n == i) {
//                 cur->next = cur->next->next;
//                 return bh->next;
//             }
//             cur = cur->next;
//         }
//         return bh->next;
//     }
// };

class Solution {
   public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* fast = head;
        ListNode* slow = dummy;
        for (int i = 0; i < n; ++i) {
            fast = fast->next;
        }
        while (fast) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};